By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 11, Issue 3, pp. 409-609

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

The Counterfeit Coin Problem Revisited

Nathan Linial and Michael Tarsi

pp. 409-415

BibTeX  Abstract Full Text:  PDF

$\Omega (n\log n)$ Lower Bounds on Length of Boolean Formulas

Michael J. Fischer, Albert R. Meyer, and Michael S. Paterson

pp. 416-427

BibTeX  Abstract Full Text:  PDF

On the Average-Case Complexity of Selecting the $k$th Best

Andrew C. Yao and F. Frances Yao

pp. 428-447

BibTeX  Abstract Full Text:  PDF

The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable

Eitan M. Gurari

pp. 448-452

BibTeX  Abstract Full Text:  PDF

The Working Set Size Distribution for the Markov Chain Model of Program Behavior

M. Hofri and P. Tzelnic

pp. 453-466

BibTeX  Abstract Full Text:  PDF

Rapid Multiplication of Rectangular Matrices

D. Coppersmith

pp. 467-471

BibTeX  Abstract Full Text:  PDF

On the Asymptotic Complexity of Matrix Multiplication

D. Coppersmith and S. Winograd

pp. 472-492

BibTeX  Abstract Full Text:  PDF

A Lubricant for Data Flow Analysis

Barry K. Rosen

pp. 493-511

BibTeX  Abstract Full Text:  PDF

Complexity Results for Scheduling Tasks in Fixed Intervals on Two Types of Machines

K. Nakajima, S. L. Hakimi, and J. K. Lenstra

pp. 512-520

BibTeX  Abstract Full Text:  PDF

Completions of Partially Ordered Sets

Bernhard Banaschewski and Evelyn Nelson

pp. 521-528

BibTeX  Abstract Full Text:  PDF

The Hamiltonian Circuit Problem is Polynomial for $4$-Connected Planar Graphs

D. Gouyou-Beauchamps

pp. 529-539

BibTeX  Abstract Full Text:  PDF

On Edge Coloring Bipartite Graphs

Richard Cole and John Hopcroft

pp. 540-546

BibTeX  Abstract Full Text:  PDF

Computational Power in Query Languages

Henry W. Davis and Leon E. Winslow

pp. 547-554

BibTeX  Abstract Full Text:  PDF

Approximation Algorithms for the Set Covering and Vertex Cover Problems

Dorit S. Hochbaum

pp. 555-556

BibTeX  Abstract Full Text:  PDF

Two Spectra of Self-Organizing Sequential Search Algorithms

Aaron M. Tenenbaum and Richard M. Nemes

pp. 557-566

BibTeX  Abstract Full Text:  PDF

Finding the Cyclic Index of an Irreducible, Nonnegative Matrix

Mikhail J. Atallah

pp. 567-570

BibTeX  Abstract Full Text:  PDF

Relativizing Time, Space, and Time-Space

Ronald V. Book, Christopher B. Wilson, and Xu Mei-Rui

pp. 571-581

BibTeX  Abstract Full Text:  PDF

Ranking and Unranking of $2$-$3$ Trees

Udai Gupta, D. T. Lee, and C. K. Wong

pp. 582-590

BibTeX  Abstract Full Text:  PDF

On Some Deterministic Space Complexity Problems

Jia-Wei Hong

pp. 591-601

BibTeX  Abstract Full Text:  PDF

Finding Augmented-Set Bases

Virgil Gligor and David Maier

pp. 602-609

BibTeX  Abstract Full Text:  PDF